package interview.cmbbank;


/**
 * description: 2023-2-26 招商银行笔试题
 *
 * @author <a href="zhaoyingling12@163.com">Simon</a>
 * @date 2023/2/26
 */
public class Test2 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.validNum(3));
    }


    static public class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * @param N int整型 字符串的长度
         * @return int整型
         */
        public int validNum(int N) {
            if (N == 1) {
                return 2;
            }
            if (N == 2) {
                return 3;
            }

            // dp[i][0] 到第i个字符串这里，有多少个 c
            // dp[i][1] 到第i个字符串这里，有多少个 M
            int[][] dp = new int[N + 1][2];
            dp[1][0] = 1;
            dp[1][1] = 1;

            for (int i = 2; i < N; i++) {
                dp[i][1] = dp[i - 1][1] + dp[i - 1][0];
                dp[i][0] = dp[i - 1][1];
            }
            return 2 * dp[N - 1][1] + dp[N - 1][0];
        }
    }
}
